#include <stdio.h>

//1、使用标志域区分队列“空”与“满”
/*在循环队列的类型结构中，增设一个整型变量tag，入队时置tag为1，出队时置tag为0
（因为只有入队操作可能导致队满，也只有出队操作可能导致队空）。
 队列Q初始时，置tag=0、front=rear=0。这样队列的4要素如下：
队空条件:Q.front==Q.rear且Q.tag==0。
队满条件:Q.front==Q.rear且Q.tag==1。
入队操作: Q.data[Q.rear]=x;Q.rear=(Q.rear+1) % MaxSize; Q.tag=1。
出队操作: x=Q.data[Q.front];Q.front=(Q.front+1) % MaxSize; Q.tag=0。*/

typedef struct {
    int data[10];
    int tag,front,rear;
}SqQueue;
//入队
int EnQueue(SqQueue &Q,int x){
    //队满
    if((Q.front == Q.rear) && (Q.tag == 1)){
        return 0;
    }
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % 10;
    Q.tag = 1;
    return 1;
}

//出队
int DeQueue(SqQueue &Q,int &x){
    if((Q.rear == Q.front) && (Q.tag == 0)){
        return 0;
    }
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % 10;
    Q.tag = 0;
    return 1;
}

//2、借助一个空栈将队列逆置
/*void Inverser(Stack &S,Queue &Q){
    //判断队列是否为空
    while (!QueueEmpty(Q)){
        x = DeQueue(Q);
        Push(S,x);
    }
    //判断栈是否为空
    while(!StackEmpty(S)){
        Pop(S,x);
        EnQueue(Q,x);
    }
}*/

//3、使用两个栈模拟一个队列
//入队
int EnQueue(Stack &S1,Stack &S2,int e){
    //如果栈S1不为满，则直接入栈S1
    if(!StackOverflow(S1)){
        Push(S1,e);
        return 1;
    }
    //如果S1栈满且栈S2不为空
    if(StackOverflow(S1) && !StackEmpty(S2)){
        printf"队列已满";
        return 0;
    }
    //S1满且S2为空，将S1中的元素全部放入S2，然后将需要入队的元素放入S1
    if(StackOverflow(S1) && StackEmpty(S2)){
        while(!StackEmpty(S1)){
            Pop(S1,x);
            Push(S2,x);
        }
    }
    Push(S1,e);
    return 1;
}

//出队
void DeQueue(Stack &S1,Stack &S2,int &x){
    if(!StackEmpty(S2)){
        Pop(S2,x);
    }else if(StackEmpty(S1)){
        printf("队列为空");
    }else{
        while(!StackEmpty(S1)){
            Pop(S1,x);
            Push(S2,x);
        }
        Pop(S2,x);
    }
}

//判断队列为空
int QueueEmpty(Stack S1,Stack S2){
    if(StackEmpty(S1) && StackEmpty(S2)){
        return 1;
    }else{
        return 0;
    }
}